In a predictive data coding method, data compression efficiency increases as the accuracy in prediction of each pixel value becomes higher. The prediction accuracy can be raised by increasing the number of pixels that are referred in the prediction process. A pixel that is referred in the prediction process will be notified as “a reference pixel” hereafter. The prediction accuracy can be raised also by optimizing the position pattern of reference pixels.
FIG. 2 shows a position pattern of reference pixels in the JBIG (Joint Bi-level Image Experts Group) coding architecture. Here, JBIG is the international standardization body for bi-level image coding where each pixel of an image takes only a binary value of either “one” or “zero”. The position pattern of reference pixels mentioned above will be referred as a “template” hereafter.
In FIG. 2, the square with hatches shows the noticed pixel, and squares p1 to p9 and the square “A” show reference pixels. Among these 10 reference pixels, the pixel denoted by A is called an AT (adaptive template) pixel, and this pixel is allowed to move to any arbitrary position among nearly 256×256 pixel positions depicted in the figure. In most image coding systems using JBIG coding architecture, however, the AT pixel position is restricted to move to one of the eight squares with a cross as shown in the figure, since it is very difficult and it requires much calculation cost to find the most appropriate position for the AT pixel among vast number of possible positions. In the JBIG recommendation document, a method that uses surrounding pixels having the strongest correlation with the noticed pixel is recommended as the AT pixel position determination method.
In compression coding of images such as characters or figures, using a template wherein all reference pixels are placed close to the noticed pixel is generally effective for improving accuracy of prediction (see Kato, et al: An Adaptive Markov Model Coding Method for Two-level Images using Dynamic Selection of Reference Pixels, IEICE Transactions, volume J70-B, number 7). For this reason, the above-mentioned JBIG recommended template works effectively in predicting the value of the noticed pixel with high accuracy, resulting in a high data compression rate.
In compression coding of natural images, however, higher prediction accuracy can be obtained in many cases by placing reference pixels at scattered positions in a wider area of the image. In this case, how to place reference pixels in scattered positions depends largely on the nature of the image. In a two-level image that is coded by using the cluster type dithering, for example, a higher compression rate cannot be obtained unless the reference pixel position distribution reflects not only features resulting from the image nature but also the periodical features resulting from dithering, since pixels with strong correlation periodically appear in the image when dithering is applied. Since an image generated by one of other dithering types, such as the vortex type, the Bayer type or the error scattering type, has also features peculiar to each coding method used, it is necessary to use a specific template corresponding to the coding method used, in order to attain higher data compression efficiency.
Unfortunately, however, when a bi-level coded natural image is given, it is very difficult to know which type of dithering has been used for coding that image. Furthermore, it is almost impossible to generate an optimum template through simple calculation, considering features arising from the pattern of the image. This is the reason why so many architectures to realize high data compression rate in image coding have been proposed.
For example, in the method proposed by Kato et al. of Utsunomiya University or in the method proposed in U.S. Pat. No. 5,023,611 by Lucent Technologies Inc., the number of coincidence between the value of the noticed pixel and the value of a pixel at one of the positions surrounding the noticed pixel is counted for each pixel in the two-level image, and when the counting results satisfy a specified condition during the compression procedure, pixels at the surrounding position having larger coincidence numbers are included in the new template as reference pixels, in order of coincidence number value.
Besides the method of changing templates successively as mentioned above, a method to determine a template based on the correlation amplitudes of surrounding pixels that are obtained before compression for the whole image, and the method to select a template that is matched to the image information among previously prepared templates are cited in Kokai No. 6-90363 by Ricoh Company, Limited.
However, methods to determine a template simply based on the amplitude of the correlation between surrounding pixels and the noticed pixel cannot determine the optimum template for a two-level image that is coded by the cluster type dithering method. This is because a template determined simply by correlation amplitude usually becomes the one around which reference pixels are densely crowded as shown in FIG. 1(a) since correlation between pixels within the same cluster is stronger, despite correlation between plural clusters should be considered.
On the contrary, in the method proposed in Kokai No. 5-30362 by Fujitsu Ltd., distance between the run up to the noticed pixel and the preceding run with the same color is used as the measure of periodicity. Here, a “run” means a string of pixels where the same pixel value continues on the same scanning line. This method, however, cannot work effectively when the image has no periodicity.
In the method proposed in Kokai No. 11-243491 by Mitsubishi Heavy Industries Ltd., the multiple regression analysis and a genetic algorithm using the compression rate as the evaluation function are used for the optimization of the template, considering both the mesh point structure and the features arising from the image pattern. Genetic algorithms are calculation methods in modeling biological evolution or adaptation in the nature, and also applied to artificial intelligence as powerful means of seeking. By using a genetic algorithm, it becomes possible to find an optimum template among a vast number of possible candidates.
The proposed method, however, has a problem that the processing speed is extremely slow. This problem arises from the implementation of a genetic algorithm. In the calculation process of a genetic algorithm, a population consisting of a plural number of solution candidates is first prepared, each candidate is evaluated and then a new population is generated based of the evaluation results. This first calculation cycle is carried out to obtain the first generation of the solution, then, recurrent similar calculation cycles are carried out to obtain each new generation until a specified finishing condition is satisfied. Consequently, this method requires evaluation time expressed by (the size of the population)×(the number of the generations).
Meanwhile, in the method proposed in Kokai No. 11-243491, it is necessary to compress once the whole noticed image and to calculate the resultant compression rate before finishing one stage of evaluation, since the method uses the compression rate as the evaluation measure. For this reason, the calculation time required for optimizing the template in this method becomes (the size of the population)×(the number of the generations) times larger than the calculation time without optimizing. For example, if the size of the population is 30 and the generation number is 100, then, the calculation time required for optimizing the template in this method becomes 3,000 times larger than the calculation time without optimizing.
If one of above-mentioned genetic algorithms is applied to an image transmission system such as the facsimile, optimizing the template for compression by using the genetic algorithm takes even much more time than required for the transmission of the whole image data without compression. Likewise, it is by no means practical to use those methods as explained for compressing an image with a size of several hundred Giga-bytes, an image for printing, for example, since those methods require a vast amount of time for calculation.
The purpose of this invention is to solve such problems in predictive coding as mentioned above, or to provide a method of adaptively adjusting a template (a position pattern of reference pixels) in order to obtain always high data compression rate for various kinds of image information.